package 算法shiyan.shiayn3;/**
 * ************************************************************************
 * 项目名称: projectweb <br>
 * 文件名称:  <br>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br>
 * 文件创建：1913040634刘世锦  <br>
 * 创建时间: 2021/4/15 <br>
 *
 * @version v1.0 <br>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br>
 * ************************************************************************
 */


/**
 * @ProjectName: projectweb
 * @ClassName: 堆排序
 * @Author: 1913040634刘世锦
 * @Date: 2021/4/15 21:16 .
 * @version v1.0
 */
import java.util.Arrays;
public class 堆排序 {
    public static void main(String[] args) {
        int [] a = {5,4,3,2,1};
        heap( a);
        System.out.println("堆排序："+Arrays.toString(a));
    }

    public static void heap(int []a){  //创建堆
        for (int i = (a.length-1)/2; i >=0 ; i--) {
            adjustheap(a,i,a.length);
        }
        for (int i = a.length-1; i >0 ; i--) {
            int t = a[0];
            a[0] = a[i];
            a[i] = t;
            adjustheap(a,0,i);
        }



    }
    public static void adjustheap(int []a , int l,int n){ //调整大顶堆
        int i =l;//要筛节点
        int j = 2*i+1;//左节点
        while (j <n){
            if(a[j]<a[j+1]&&j<n-1 ) j++;
            if (a[j]>a[i]){
                int q = a[i];
                a[i] = a[j];
                a[j] = q;  //交换了
                i =j;   //记住被交换的位置 左节点 就是之后的代换节点
                j = 2*i+1;
            }else{
                break;
            }

        }

    }
}
